\part{最优化理论}
\chapter{拉格朗日函数}
问题的表述

\begin{align*}
& \max_x\; F(\bm{x})\\
& s.t.\quad c = G(\bm{x})=p_1x_1+p_2x_2
\end{align*}

其中，$\bm{x}=(x_1,x_2)' $ 。

图形化；

回忆泰勒定理\footnote{设$ f(x) $在含有$ x_0 $的某个开区间$ I $内有直到$ n+1 $阶的导数，则对任一$ x\in I $,\[ f(x)=f(x_0)+f'(x_0)(x-x_0)+\frac{f''(x_0)}{2!}(x-x_0)^2+\cdots+\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n+R_n(x) \]其中$ R_n(x) =\frac{f^{(n+1)}(\xi)}{(n+1)!}(x-x_0)^{n+1}$($ \xi $在$ x_0 $与$ x $之间)，为高阶无穷小。}（泰勒展开），
\begin{equation}\label{opt_eq1}
dF(\bm{x})=F_1(\bm{x})dx_1+F_2(\bm{x})dx_2
\end{equation}

类似地，对约束$G(x) $也有一个这样的变动，
\begin{equation}\label{opt_eq2}
0 = dG(\bm{x})=G_1(\bm{x})dx_1+G_2(\bm{x})dx_2
\end{equation}

对于约束条件而言，对于任意某个点如$ \bm{x}^* $，它的变化不能使得$ G $发生变化。譬如将$ F $看作效用，$G$看作总收入，$ \bm{x} $看作消费品的选择，消费品选择的变化不能影响总收入的变化。即\eqref{opt_eq2}式要等于0，
\[
G_1(\bm{x}^*)dx_1=-G_2(\bm{x}^*)dx_2
\]
如果令，
\[
G_1(\bm{x}^*)dx_1=-G_2(\bm{x}^*)dx_2=dc
\]
那么，就有，
\[
dx_1=\frac{dc}{G_1(\bm{x}^*)},dx_2=-\frac{dc}{G_2(\bm{x}^*)}
\]
那么将上式代入\eqref{opt_eq1}式，有，
\[
dF(\bm{x}^*)=\left [\frac{F_1(\bm{x}^*)}{G_1(\bm{x}^*)}-\frac{F_2(\bm{x}^*)}{G_2(\bm{x}^*)}\right ]dc
\]
如果中括号里的式子不为0，那么只要选择$dc$与中括号里的式子同号\footnote{比如中括号为正数，我就可以增加或减少$ x_1 $使得$ dx_1 $为正或为负来改变$ dc $的符号，这取决于与$ G_1(\bm{x}^*) $的符号。}，就可以使得$F(\bm{x})$增加。可见， 中括号里的式子应该为0，即
\begin{equation}\label{opt_eq3}
\frac{F_1(\bm{x}^*)}{G_1(\bm{x}^*)}=\frac{F_2(\bm{x}^*)}{G_2(\bm{x}^*)}
\end{equation}
如果令，
\[
\frac{F_1(\bm{x}^*)}{G_1(\bm{x}^*)}=\frac{F_2(\bm{x}^*)}{G_2(\bm{x}^*)}=\lambda
\]
那么\eqref{opt_eq3}式就可以写成两个方程，即，
\begin{equation}\label{opt_eq4}
F_j(\bm{x}^*)=\lambda G_j(\bm{x}^*),\quad j=1,2
\end{equation}

以上是一种推导，为方便记忆，可以总结成一个拉格朗日定理，针对最优化函数和约束条件，定义一个拉格朗日函数，
\[
L(\bm{x},\lambda)=F(\bm{x})+\lambda[c-G(\bm{x})]
\]
记$L$的偏导为，
\[
L_j\equiv \frac{\partial L}{\partial x_j},L_{\lambda}\equiv \frac{\partial L}{\partial \lambda}
\]
那么，有，
\begin{align*}
& L_j(\bm{x},\lambda)=F_j(\bm{x})-\lambda G_j(\bm{x})\\
& L_{\lambda}(\bm{x},\lambda)=c-G(\bm{x})
\end{align*}

如果分别令$L_j=0,L_{\lambda}=0 $，那么上述第一个式子就是\eqref{opt_eq4}式，第二个式子就是约束条件。这就是拉格朗日定理。
\section{相切法}
图\ref{pic_tan}中$ G(\bm{x}) $是约束曲线，$ F(\bm{x}) $是不同$ \bm{x} $组合下的等高线，即$ F(\bm{x})=v $。

先看约束曲线$ G(\bm{x})=c $，在这条曲线上移动(即$ \bm{x} $发生变化)，不会使得$ G(\bm{x}) $发生改变，即$ dG(\bm{x})=0=G_1(\bm{x})dx_1+G_2(\bm{x})dx_2 $。从而可以得到这条曲线的斜率，
\[ \frac{dx_2}{dx_1}=-\frac{G_1(\bm{x})}{G_2(\bm{x})} \]

类似的，对于等高线$ F(\bm{x})=v $，在这条曲线上移动，也不会使得其值发生改变，它也有，
\[ \frac{dx_2}{dx_1}=-\frac{F_1(\bm{x})}{F_2(\bm{x})} \]

而在最优值$ \bm{x}^* $处，约束曲线的斜率等于等值曲线的斜率。即
\[ \frac{F_1(\bm{x}^*)}{G_1(\bm{x}^*)}=\frac{F_2(\bm{x}^*)}{G_2(\bm{x}^*)} \]
它与\eqref{opt_eq3}式是一致的。

\begin{figure}[H]
\includegraphics[scale=1]{相切图.pdf}
\caption{相切解}\label{pic_tan}
\end{figure}
\section{必要条件和充分条件}
上述推导对最小化问题也是成立的，因此，上述结论仅仅是一个必要条件。这时往往要用到二阶条件。比如最大值是二阶导数小于0.

\paragraph{单变量情形}为推导二阶条件，此处以无约束最大化问题为例。现在在最优值$ x^* $处，将目标函数$ F(x) $二阶泰勒展开，有，
\[ F(x)=F(x^*)+F'(x^*)(x-x^*)+\frac{1}{2}F''(x^*)(x-x^*)^2+\cdots \]

因为，最优化的一阶条件为0，因此上式又可以写成，
\[ F(x)-F(x^*)= \frac{1}{2}F''(x^*)(x-x^*)^2 \]

如果$ F''(x)>0 $，就意味着此时$ x^* $并不能使得$ F(x) $取得最大值。因此，必然有$ F''(x)< 0 $，它是$ F(x) $取最大值的二阶充分条件。如果$ F''(x)=0 $，就需要观察更高阶的导数，此处不再继续讨论。

\paragraph{多变量情形}泰勒展开为，
\[ F(\bm{x})=F(\bm{x}^*)+F^T_{\bm{x}}(\bm{x}^*)\cdot (\bm{x}-\bm{x}^*)+\frac{1}{2}(\bm{x}-\bm{x}^*)^T\cdot F_{\bm{xx}'}(\bm{x}^*)\cdot (\bm{x}-\bm{x}^*) \]

其中，$ F(\bm{x}) $是列向量，$ F_{\bm{xx}'} $是对称方阵。类似地，有，
\[ F(\bm{x})-F(\bm{x}^*)=\frac{1}{2}(\bm{x}-\bm{x}^*)^TF_{\bm{xx}'}(\bm{x}^*)(\bm{x}-\bm{x}^*) \]
这要求二次型$ \frac{1}{2}(\bm{x}-\bm{x}^*)^TF_{\bm{xx}'}(\bm{x}^*)(\bm{x}-\bm{x}^*) $必须为负，这意味着矩阵$ F_{\bm{xx}'} $必然是负定的。

\chapter{多变量的拓展和库恩塔克定理}
\section{多变量和多约束条件的拓展}
上述拉格朗日定理可以扩展至多变量和多约束的情景中。譬如有$n$个选择变量$(x_1,x_2,\cdots,x_n) $，$m$个约束$G^i(x)=c_i,i=1,2,\cdots,m $，那么可以为每一个约束定义一个乘子$\lambda_i $，拉格朗日函数可以定义为，
\[
L(x_1,x_2,\cdots,x_n,\lambda_1,\lambda_2,\cdots,\lambda_m)=F(x_1,x_2,\cdots,x_n)+\sum_{i=1}^m\lambda_i[c_i-G^i(x_1,\cdots,x_n)]
\]
一阶必要条件则为，

\begin{align}\label{opt_eq_L1}
& L_{x_j}(x,\lambda)=0,j=1,\cdots,n\\\label{opt_eq_L2}
& L_{\lambda_i}(x,\lambda_i)=c_i-G^i(x)=0,i=1,\cdots,m
\end{align}


例：消费者在价格分别为$p$和$q$的两种商品$x$和$y$上进行选择，其收入为$I$，因此预算约束为，
\[I=px+qy\]

如果他的效用函数为
\[U(x,y)=\alpha\ln (x)+\beta\ln (y) \]

请问，他应该分别买多少$x$和$y$？见\lstinline|lagrange.mw|.
\[x= \frac{\alpha  I}{p (\alpha +\beta )},y= \frac{\beta  I}{q (\alpha +\beta )},\lambda = \frac{\alpha +\beta }{I}\]

这是mathmatica软件的求解代码：
\begin{lstlisting}
Uf := \[Alpha]*Log[x] + \[Beta]*Log[y];
f1 := D[Uf + \[Lambda]*(Inc - p*x - q*y), x];
f2 := D[Uf + \[Lambda]*(Inc - p*x - q*y), y];
f3 := Inc - p*x - q*y;
Solve[{f1 == 0, f2 == 0, f3 == 0}, {x, y, \[Lambda]}]
\end{lstlisting}
\section{库恩塔克条件}
\paragraph{$ \bm{x} $非负} 如果我们假定向量$ \bm{x} $必须非负(这在经济学问题中很常见)，那么按照我们前面的方法,根据最优值$ \bm{x}^* $的取值情况，会出现两种状态：
\begin{itemize}
	\item 如果按\eqref{opt_eq_L1}式和\eqref{opt_eq_L2}式算出的最优值$ \bm{x}^* $恰好全部为正，则此时的非负约束不起作用，以前该怎样还是怎样。
	\item 如果按\eqref{opt_eq_L1}式和\eqref{opt_eq_L2}式算出的最优值$ \bm{x}^* $部分出现了负值，比如$ x^*_1 $为负，此时非负约束起作用，$ x_1^* $只能取0\footnote{可以从商品消费的角度来理解，不能取正值，因为任何正值再减少一点点总会使得目标函数变大，最终商品减少为0。}。同时，有下式成立(见附录\ref{app_kt})：
	\begin{equation}\label{opt_eq_kt}
	L_1(\bm{x}^*)\equiv F_1(\bm{x}^*)-\sum_{i=1}^m\lambda_iG_1^i(\bm{x}^*)\le 0	
	\end{equation}
\end{itemize}

这就意味着，一旦$ x_j^*>0 $，则必有$ L_j(\bm{x}^*)=0 $；一旦$ x^*_j=0 $，则必有$ L_j(\bm{x}^*)\le 0 $。也就是说$ x^*_j,L_j(\bm{x}^*) $至少有一个为0。而这可以在数学上表达为，
\begin{align}
x^*_j\cdot L_j(\bm{x}^*)=0\\	\label{opt_eq_slack}
x^*\ge 0, L_j(\bm{x}^*)\le 0
\end{align}

因为\eqref{opt_eq_slack}式不可能两个不等式同时成立，总有一个等式成立，类似\eqref{opt_eq_slack}的式子被称为\emph{互补松弛}的。即一个约束是松的($ \ne 0 $)，则另一个约束必然是紧的($ =0 $)。

\paragraph{更一般的不等式约束}进一步考虑更一般的约束。比如对于第一个约束有，
\[ G^1(\bm{x})\le c_1 \]
经济含义为收入不一定要全部花完。可以定义新变量$ x_{n+1} $(这个定义很显然形成了一个新的等式约束),
\[ x_{n+1}=c_1-G^1(\bm{x}) \]
而$ x_{n+1}\ge 0 $，这又回到了前面的非负约束问题。那么，有拉格朗日函数，
\[ \hat{L}(\bm{x})=F(\bm{x})+\lambda_1[c_1-G^1(\bm{x})-x_{n+1}]+\sum_{i=2}^m\lambda_i[c_i-G^i(\bm{x})] \]

很显然，依据互补松弛条件\eqref{opt_eq_slack}式，这意味着，
\[ x_{n+1}\ge 0, \frac{\partial L}{\partial x_{n+1}}=-\lambda_1\le 0 \]
为便于记忆，可以看到，如果不引入$ x_{n+1} $，那么拉格朗日函数应该写成，
\[ L(\bm{x})=F(\bm{x})+\lambda_1[c_1-G^1(\bm{x})]+\sum_{i=2}^m\lambda_i[c_i-G^i(\bm{x})] \]
那么，有，
\begin{equation}\label{opt_eq_slack2}
x_{n+1}=c_1-G^1(\bm{x})=\frac{\partial L}{\partial \lambda_1}\ge 0, \lambda_1\ge 0	
\end{equation}
这是关于一般的不等式约束的互补松弛条件。

对上述两种情况做一个总结，则有库恩-塔克定理。

\begin{theorem}{库恩-塔克定理}{opt_kt}
	 对于$ n $维向量$\bm{x}  $，$ m $维向量$ c $，$ F $是标量函数,$ G $是$ m $维向量值函数。定义
	\[ L(\bm{x},\bm{\lambda})=F(\bm{x})+\bm{\lambda}[\bm{c}-G(\bm{x})] \]
	在约束$ G(\bm{x})\le c,\bm{x}\ge 0 $下最大化$ F(\bm{x}) $，则有，
	\begin{align*}
		L_{\bm{x}}(\bm{x}^*)\le 0,\bm{x}^*\ge 0\hspace{2em}\text{满足互补松弛条件}\\
				L_{\bm{\lambda}}(\bm{x}^*)\ge 0,\bm{\lambda}^*\ge 0\hspace{2em}\text{满足互补松弛条件}
	\end{align*}
\end{theorem}

\section{一个例子}
假定两种商品$ x,y $，数量必须非负，价格$ p,q $，都为正。其最优规划为，
\begin{align*}
	\max_{x,y}\quad U(x,y)=y+a\ln(x)\\
	s.t.\quad px+qy\le I\\
	x\ge 0\\
	y\ge 0
\end{align*}

像这样其中一个商品数量是线性的效用函数，我们称为拟线性偏好。该最优规划的拉格朗日函数为，
\[ L(x,y,\lambda)=y+a\ln(x)+\lambda(I-px-qy) \]

根据库恩-塔克定理，有，
\begin{align}\label{eq_opt_x}
	\frac{a}{x}-\lambda p\le 0,x\ge 0\\\label{eq_opt_y}
	1-\lambda q\le 0,y\ge 0\\\label{eq_opt_I}
	I-px-qy\ge 0, \lambda \ge 0
\end{align}

因为有两个非负变量和一个不等式约束，所以我们需要讨论$ 2^3=8 $种情况，即$ x $松紧，$ y $松紧和$ \lambda $松紧。但实际上在经济学中，你可以轻易地排除掉很多情况。

首先看看$ \lambda $的松紧。$ \lambda $不可能是紧的，因为一旦$ \lambda=0 $，根据\eqref{eq_opt_x}式就意味着$ a/x<0 $，这显然是不对的。因此，只需要讨论4种情况了。

然后，看看$ x $的松紧。如果$ x=0 $，则\eqref{eq_opt_x}式会出现无穷大。因此，这种情况也无需讨论了。

第三，看看$ y $的松紧。如果$ y=0 $，那么根据\eqref{eq_opt_I}式，有$ x=I/p $，联合\eqref{eq_opt_x}式意味着$ \lambda=a/I $，再带入\eqref{eq_opt_y}式得到$ I\le aq $。然后你看你系统中的参数是不是满足这种情况，如果满足，则这就是最优解的一种，如果不满足，则$ y $必然也是松的。

最后，就是要讨论$ x,y $都是松的情况。经过推导会有$ y=I/q-a $，如果$ I>aq $，则逻辑一致，否则就不对了。因此，你会发现根据参数的约束情况($ I $是大于还是小于$ aq $)，你就知道解会是哪一种。

那么，我们可以把解归纳为：
\begin{itemize}
	\item 如果$ I\le aq $，那么$ x=I/p, y =0 $；
	\item 如果$ I>aq $，那么$ x=aq/p, y = I/q-a $
\end{itemize}

这个解很有经济含义。当你的收入很低时，你的收入都花在了$ x $上，当你的收入超过某个阈值时，你会开始购买$ y $。很多时候，你建模时，可能会很想要这个特征。


\chapter{包络定理}
\section{证明}
包络定理研究的是参数对最优值的影响。在最优值处，目标函数的值为$F(x^*) $，这个值实际上也是参数的函数，即可以定义，
\[V(\alpha)=F(x^*(\alpha),\alpha)\]
这个函数称为最大值函数。

首先，构造拉格朗日函数，
\[
L(x,\alpha;\lambda)=F(x,\alpha)-\lambda G(x,\alpha)
\]

此处，$\alpha $是参数。针对该拉格朗日函数的一阶条件为，
\begin{align*}
& \frac{\partial L}{\partial x_i}=F_i(x,\alpha)-\lambda G_i(x,\alpha)=0\\
& \frac{\partial L}{\partial \lambda}= G(x,\alpha)=0
\end{align*}

假设，已经得到了最优值$x^*=x^*(\alpha) $，那么针对最大值函数$V(\alpha)=F(x^*(\alpha),\alpha) $两边对参数求导，有，
\begin{equation}\label{eq5}
\frac{\partial V}{\partial \alpha}=\sum F_i\frac{\partial x^*_i}{\partial \alpha}+F_{\alpha}=\sum \lambda G_i\frac{\partial x^*_i}{\partial \alpha}+F_{\alpha}
\end{equation}

再来观察约束$G(x^*(\alpha),\alpha)=0 $，两边对$\alpha $求导，有，
\begin{equation}\label{eq6}
\sum G_i\frac{\partial x^*_i}{\partial \alpha}+G_{\alpha}=0
\end{equation}

将\eqref{eq6}式代入\eqref{eq5}式，可得，
\[ \frac{\partial V}{\partial \alpha}=F_{\alpha}-\lambda G_{\alpha}=L_{\alpha}(x^*,\alpha) \]
即参数 对最大值的影响，就等于拉格朗日函数直接对参数求偏导，并在最优解处取值。

\paragraph{图形说明}
\begin{figure}[H]
	\includegraphics[scale=0.5]{envelope.png}
\end{figure}

这个图的横坐标就是参数$ \theta $，纵坐标就是最大值$ v $。那么最优值函数可以写为，
\[ V(\theta)=\max_x\{F(x,\theta)|G(x)=c\} \]

\begin{itemize}
	\item 注意两个函数:
	\begin{itemize}
		\item 	$ V(\theta) $是最大值函数，但是它会随着参数$ \theta $的变化，最大值$ v $会发生变化，这就是图中最上面的那根线。
		\item 还要注意随着$ \theta $的变化,最优被选择的变量$ x $也是会变的，这可以写成函数$ \bar x = X(\theta) $。因此，为理解这种$\theta $变，从而$ x $变，从而$ v $变的过程，最大值函数还可以写成，
\[ V(\theta)=F(X(\theta),\theta) \]
	\end{itemize}
\item 图中的$ F(\bar x^1,\theta) $表示的是尽管$ \theta $变，但$ x $不变时(即就取参数等于$ \theta_1 $时的最优值$ \bar{x}^1 $这个值)，$ v $的变化。
\item 很显然，$ V(\theta) $这根曲线一定跟$ F(\bar{x}^1,\theta) $这根曲线切在$ \theta_1 $点，而且，如果$ \theta $要发生变化，$ V(\theta) $这根曲线一定要在$ F(\bar{x}^1,\theta) $这根曲线上面。
\item $ F(\bar{x}^2,\theta) $具有类似的含义。那么你会发现最优值函数曲线是值函数曲线的上包络线，这就是它为啥取名包络定理的原因。
\end{itemize}


\section{影子价格}
\begin{definition}{比较静态分析}{int}
	比较最优解如何随着参数的变动而变动的一般方法，称为比较静态分析。
\end{definition}
拉格朗日乘子为一个非常重要的比较静态问题提供了答案。比如在一个计划经济中，选择要素投入以最大化社会福利函数，总要素投入约束为$ c $。
\begin{align*}
	\max_{x_1,x_2} \quad &F(x_1,x_2)\\
	s.t.\quad &c = p_1x_1+p_2x_2
\end{align*}
该最优规划有拉格朗日函数
\[ L=F(x_1,x_2)+\lambda\cdot (c-p_1x_1-p_2x_2) \]

很显然，总投入$ c $在这里是一个参数。那么，依据包络定理，有
\[ \frac{\partial V}{\partial c}=\frac{\partial L}{\partial c}=\lambda \]

可以看到$ \lambda $就是总投入的边际效用。而且因为$ dV = \lambda dc $，$ \lambda $也可以看作是总投入量的以社会福利单位来衡量的价格(价值=价格$ \times $数量)。各类资源是有价格的，这个价格就是$ \lambda $，它也被称为影子价格。

\chapter{凸集、凸函数、凹函数、拟凸函数和拟凹函数}
\section{凹函数和凸函数}
前面已经看到，判断最大值或最小值的充分条件，从函数曲线的形态上看，是看它如何弯曲。如果是U形，一阶条件对应的是最小值。如果是倒U形，则一阶条件对应的是最大值。因此，一个在整个定义域中给出峰形（谷底）的函数被称作凹（凸）函数。

正式的数学定义如下，
\begin{definition}{凹函数和凸函数}{int}
对于函数$ f $定义域内任意两个不同的点$ u,v $，且对于$ 0<\theta<1 $，当且仅当，
\[ \underbrace{\theta f(u)+(1-\theta)f(v)}_{\text{线段高度}}\le\underbrace{ f[\theta u+(1-\theta)v}_{\text{弧的高度}} \]
时，$ f $为凹函数。
\[ \underbrace{\theta f(u)+(1-\theta)f(v)}_{\text{线段高度}}\ge \underbrace{f[\theta u+(1-\theta)v}_{\text{弧的高度}} \]
时，$ f $为凸函数。
\end{definition}
注意，严格凹或凸函数不允许函数出现平坦部分。

因此，当一阶条件满足时，如果目标函数是凹的，则由一阶条件得到的最优点必然对应最大值。如果是严格凹的，则对应的唯一的最大值。

\section{凸集和凸（凹）函数}
\begin{figure}[H]
\includegraphics[scale=0.5]{separate.png}
\end{figure}

可以看到图中的曲线都是向外鼓出的，并且不会弯回来再次相遇。我们应该在数学上给这种形态一种定义。从代数上看，这意味着对于前述2维空间的点集$ S $中的任意两点$ x^a=(x_1^a,x_2^a),x^b=(x_1^b,x_2^b) $，以及闭区间$ [0,1] $上的任意实数，点$ \theta x^a+(1-\theta)x^b $仍在集合$ S $内，这样的集合就被称为凸的。注意图中的两个集合都是凸的。

下图是一些有趣的例子，有些是凸的，有些则不是。
\begin{figure}[H]\centering
	\includegraphics[scale=0.7]{tuset.png}
\end{figure}
\begin{itemize}
	\item 在描述函数时，“凸”是确定一条曲线或曲面如何弯曲。
	\item 在描述集合时，“凸”是确定集合中的点如何“填充”到一起，不能出现孔，边缘不能缩进。
\end{itemize}


凸集和凸（凹）函数的联系：
\begin{itemize}
	\item 定义凸（凹）函数时，定义域必然为凸集。
	\item 若$ f(x) $为凸函数，则对于任意常数$ k $，它可以引致一个凸集，
	\[ S^{\le}\equiv \{x|f(x)\le k\} \]
	\item 若$ g(x) $为凹函数，则对于任意常数$ k $，它可以引致一个凸集，
	\[ S^{\ge}\equiv \{x|g(x)\ge k\} \]
\end{itemize}
\begin{figure}[H]\centering
	\includegraphics[scale=0.7]{aotu.png}
\end{figure}

\section{拟凹和拟凸函数}
无约束情况下，已知目标函数的凹凸性，可以不用检查二阶条件。在约束情况下，如果目标函数具有拟凹（凸）性，也不用检查二阶条件就能知道是最大值或最小值。

拟凹性（拟凸性）比凹（凸）性是更弱的条件。这是必然的，因为约束极值免除的二阶充分条件（仅对满足约束的$ x $而言，要求其满足负定）比无约束免除的二阶充分条件（对所有的$ x $都要满足负定）更弱。

\begin{definition}{拟凹（凸）函数}{quasiconcavity}
	令$ u,v $是函数$ f $在凸集定义域中的两个不同的点，定义域中的线段$ uv $在函数$ f $上给出弧段$ MN $，使得点$ N $高于或等于$ M $。
	\begin{itemize}
		\item 	如果弧段$ MN $上除点$ M $和$ N $外的所有点的高度均高于或等于点$ M $的高度（低于或等于点$ N $的高度），则称函数$ f $是拟凹（拟凸）函数。
		\item  如果弧段$ MN $上除点$ M $和$ N $外的所有点的高度均严格高于或等于点$ M $的高度（低于或等于点$ N $的高度），则称函数$ f $是严格拟凹（拟凸）函数。
	\end{itemize}

\end{definition}


\begin{figure}[H]\centering
	\includegraphics[scale=0.7]{niao.png}
\end{figure}
\begin{itemize}
	\item (a)图是严格拟凹函数，但不是拟凸函数
	\item (b)图是严格拟凸函数，但不是拟凹函数
	\item （c）图满足拟凹，但不满足严格拟凹。
\end{itemize}

如果目标函数是严格拟凹函数，约束条件对应的点集是凸集，则一阶条件对应的最优值是最大值。



\chapter{最大值原理}
\section{推导}
一般有一个单期的目标函数如$F(y_t,z_t,t) $需要优化，该目标函数的特点就是它只依赖于当期变量，于是整个时间维度上的最优化可以表示为，
\begin{equation}\label{mv_eq7}
\sum_{t=0}^T F(y_t,z_t,t)
\end{equation}
这类问题有一个很大的特点，就是变量区分为存量和流量两个维度。存量维度的一般称为状态变量，流量维度的称为控制变量，这些变量之间存在一个如下约束，
\begin{equation}\label{mv_eq8}
y_{t+1}-y_t=Q(y_t,z_t,t)
\end{equation}

除此之外，我们还具有先前的一般约束，
\begin{equation}\label{mv_eq9}
G(y_t,z_t,t)=0
\end{equation}

于是若记$ \mathcal{L} $为跨期问题的拉格朗日函数，那么
\begin{equation}\label{mv_eq10}
\mathcal L=\sum_{t=0}^T \{F(y_t,z_t,t) +\pi_{t+1}[y_t+Q(y_t,z_t,t)-y_{t+1}]-\lambda_tG(y_t,z_t,t)\}
\end{equation}

$\mathcal L $中的变量包括$y_t,z_t,\lambda_t,\pi_{t+1} $。实际上，我们的问题在于选择$y_t,z_t $来使目标函数最大化，关于$z_t $（ $t=0,1,\cdots,T $）的一阶条件非常简单，
\begin{equation}\label{eq11}
\frac{\partial \mathcal L}{\partial z_t}\equiv F_z(y_t,z_t,t)+\pi_{t+1}Q_z(y_t,z_t,t)-\lambda_tG_z(y_t,z_t,t)=0
\end{equation}

关于$y_t $的一阶条件略显复杂，譬如因为$y_1 $出现在了$F,Q$和$G$中，于是在$t=1$的时候有$\pi_2y_1 $项，实际上在$t=0$的时候，又有$-\pi_1y_1 $项，这样的话，求导会很麻烦。但可以重新整理\eqref{mv_eq10}式，使得每一个$y_t $只出现在一项中。取\eqref{mv_eq10}式中我们所关注的一部分，
\begin{align*}
\sum_{t=0}^T \pi_{t+1} & (y_t-y_{t+1})\\
& = \pi_1(y_0-y_1)+\pi_2(y_1-y_2)+\cdots+\pi_{T+1}(y_T-y_{T+1})\\
& = y_0\pi_1+y_1(\pi_2-\pi_1)+\cdots+y_T(\pi_{T+1}-\pi_T)-y_{T+1}\pi_{T+1}\\
& = \sum_{t=1}^Ty_t(\pi_{t+1}-\pi_t)+y_0\pi_1-y_{T+1}\pi_{T+1}
\end{align*}

于是\eqref{mv_eq10}式就可以写成，
\begin{align*}
\mathcal L= & \sum_{t=0}^T \{F(y_t,z_t,t) +\pi_{t+1}Q(y_t,z_t,t)-\lambda_tG(y_t,z_t,t)\}+\sum_{t=1}^{T}y_t(\pi_{t+1}-\pi_t)+\\
& +y_0\pi_1-y_{T+1}\pi_{T+1}
\end{align*}

求和符号外的只跟$y_0,y_{T+1} $有关，而它们又不是选择变量（第一个不用选择，最后一个没必要选择）。因此，关于$y_t $（ $t=1,\cdots,T $)的一阶条件为，
\[
\frac{\partial \mathcal L}{\partial y_t}\equiv F_y(y_t,z_t,t)+\pi_{t+1}Q_y(y_t,z_t,t)+\pi_{t+1}-\pi_t-\lambda_tG_y(y_t,z_t,t)=0
\]
也即，
\begin{equation}\label{eq12}
\pi_{t+1}-\pi_t=-[F_y(y_t,z_t,t)+\pi_{t+1}Q_y(y_t,z_t,t)-\lambda_tG_y(y_t,z_t,t)]
\end{equation}
该式最为关键。

\section{记忆}
为方便记忆，定义汉密尔顿函数，
\begin{equation}\label{mv_eq13}
H(y_t,z_t,\pi_t,t)=F(y_t,z_t,t)+\pi_{t+1} Q(y_t,z_t,t)
\end{equation}
基于汉密尔顿函数定义新的拉格朗日函数$L$（注意此拉格朗日函数单期的），
\[
L=H(y_t,z_t,\pi_{t+1},t)-\lambda_tG(y_t,z_t,t)
\]

那么，在汉密尔顿函数的定义框架下：
\begin{itemize}
	\item 对控制变量的一阶条件\eqref{eq11}式，表明的是在时刻$t$选择控制变量$ z_t $，在\eqref{mv_eq9}式约束下最大化汉密尔顿函数。亦即，
	\[ L_{z}=0 \]
	在这个最优的$ z_t^* $下，会有一个最大值记为$H^*(y_t,\pi_{t+1},t) $。
	\item 
	原来对状态变量的一阶条件\eqref{eq12}式，就能写成，
	\begin{equation}\label{eq14}
		\pi_{t+1}-\pi_t=-L_y(y_t,z_t,\pi_{t+1},t)
	\end{equation}	
\end{itemize}

也就是说，通过引入汉密尔顿函数，我们可以对原来关于控制变量和状态变量的一阶条件换一个写法而已。

在这个单期优化问题里，只有$ z_t $是选择变量，其他都是参数，那么回忆包络定理，\eqref{eq14}式也意味着
\begin{equation}\label{mv_eq15}
\pi_{t+1}-\pi_t=-H_y^*(y_t,\pi_{t+1},t)
\end{equation}
作为一种对称，资源约束条件\eqref{mv_eq8}式也可以写成，
\begin{equation}\label{mv_eq16}
y_{t+1}-y_t=H_{\pi}^*(y_t,\pi_{t+1},t)
\end{equation}

现在来总结一下，以形成最大值原理。在约束\eqref{mv_eq8}式和\eqref{mv_eq9}式下，最大化\eqref{mv_eq7}式的一阶必要条件满足：
\begin{enumerate}
	\item 在单期约束$G=0 $下最大化由汉密尔顿函数定义的拉格朗日函数，即\eqref{eq11}式。
	\item 差分方程\eqref{mv_eq15}式和\eqref{mv_eq16}式决定了$y_t,\pi_t $的时间维度变化。	
\end{enumerate}
综上，必要条件可以总结为关于控制变量和状态变量的两个一阶条件以及两个约束条件：
\begin{align}
	\frac{\partial L}{\partial z_t}=& F_z(y_t,z_t,t)+\pi_{t+1}Q_z(y_t,z_t,t)-\lambda_tG_z(y_t,z_t,t)=0\\
	\frac{\partial L}{\partial y_t}=& -(\pi_{t+1}-\pi_t)\\
	y_{t+1}-y_t=&Q(y_t,z_t,t)\\
	G(y_t,z_t,t)=&0
\end{align}
\section{横截条件}
一项资产在最后如果有剩余，说明它没有价值。如果没有剩余，说明有价值。即
\[
y_{T+1}\ge 0,\pi_{T+1}\ge 0
\]

满足互补松弛条件。这种关于终端存量和他们影子价格的条件通常称为横截条件。

往连续时间的推广
对应\eqref{mv_eq7}式的目标函数可以写为，
\[
\int_0^T F(y_t,z_t,t)dt
\]

然后定义汉密尔顿函数如\eqref{mv_eq13}式相同，那么最大值原理依然成立，第一个条件即$z_t $在约束$G=0 $下最大化$H$。同时在变量上方加一个点表示该变量对时间求导，那么对应\eqref{mv_eq15}式和\eqref{mv_eq16}式的一阶条件即为，
\[
\dot{y}=H^*_{\pi}(y_t,\pi_t,t)
\]
\[
\dot \pi=-H^*_y(y_t,\pi_t,t)
\]


\section{例题}
例：一个寿命为$T$的工人，生命期间将赚取常数$w$的工资，该储蓄有常数$r$的利率，所以当他的资本存量为$k$时，他收入的流量就是$w+rk$。如果他的消费是c，那么他资本积累就由下式决定，
\[
\dot k=w+rk-c
\]

状态变量是$k$,控制变量是$c$。如果他没有遗产也没有遗赠，即终端条件或者说横截条件是，
\[
k(0)=k(T)=0
\]

如果瞬时效用函数是$\ln c $，效用折现率是$\rho $，那么最大化的目标为，
\[
\int_0^T \ln c\cdot e^{-\rho t}dt
\]

对于该问题，可以定义汉密尔顿函数，
\[
H=\ln c\cdot e^{-\rho t}+\pi(w+rk-c)
\]

因为这里没有一般的约束条件$ G $，因此这个汉密尔顿函数也就是拉个朗日函数。于是，首先，关于控制变量的条件为$ L_c=H_c=0 $，
\begin{equation}\label{mv_eq17}
c^{-1}e^{-\rho t}-\pi=0
\end{equation}

将计算得到的$ c $代入$ H $，可以得到最大化的汉密尔顿函数为，
\[
H^*=-(\ln \pi+\rho t)e^{-\rho t}+\pi(w+rk)-e^{-\rho t}
\]

于是关于$ \pi $ 的微分方程或者说状态变量的一阶条件为，
\begin{equation}\label{eq18}
	\dot \pi=-\frac{\partial H^*}{\partial k}=-\frac{\partial L}{\partial k}=-r\pi
\end{equation}

再加上原来的资源约束，
\[
\dot k=w+rk-\pi^{-1}e^{-\rho t}=\frac{\partial H^*}{\partial \pi}
\]

\eqref{eq18}式是最简单的变量可分离的一阶常微分方程，这样方程的通解是显然的，
\begin{equation}\label{eq19}
\pi=\pi_0e^{-r t}
\end{equation}

$\pi_0 $是一个常数，一般通过横截条件求出。

若将\eqref{eq19}式代入\eqref{mv_eq17}式，也可以发现一些特征事实，
\[
c=\pi_0^{-1}e^{(r-\rho)t}
\]

当$r>\rho $ 时，消费是不断增长的。这意味着在生命早期是$c<w $，在晚期则是$c>w $。

\chapter{动态规划的视角}
我们会在后面那一部分中详细探讨这部分的内容。

